5.2 Undirected graphs (ugraph)
1. Definition
An instance G of the data type ugraph consists of a set of nodes V and a
set of undirected edges E. Every edge e∈E is a set of two nodes
{v, w}, v and w are called the endpoints of e. With every node v is
associated the list of its adjacent edges
adj(v) = { e∈E | v∈e }.
2. Creation
G
creates an instance G of type ugraph and initializes it to the empty undirected graph.
3. Operations
Most operations are the same as for directed graphs. The following operations
are either additional or have different effects.
& truecm & truecm &
node opposite node v, edge e
returns w if
e = {v, w}, nil otherwise
4. Implementation
Undirected graphs are implemented like directed graphs by adjacency lists. The adjacency list of a node v contains all edges {v, w} of the graph. Most operations take constant time, except of all_nodes, all_edges, del_all_nodes, del_all_edges, clear, write, and read which take time O(n + m), where n is the current number of nodes and m is the current number of edges. The space requirement is O(n + m).